package leetcode

func findNthDigit(n int) int {
	// 在目标数字前，可以先大面积排除
	// 举例第n个数字出现在10000之后，
	// 则1~9我们可以直接排除掉9*1个数字
	// 10~99我们可以直接排除掉90*2个数字
	// 100~999我们可以直接排除掉900*3个数字
	// 1000~9999我们可以直接排除掉9000*4个数字
	// 10^k~(10^k)-1我们可以直接排除掉9*10^k*(k+1)个数字
	// 所以我们可以按照这个第n个数字所在的大范围
	l := 1
	start := 1
	cnt := 9
	for n > cnt*l {
		n -= cnt * l
		l++
		cnt *= 10
		start *= 10
	}

	// 然后此时知道了还剩多少个数字需要查找，该范围每个数有l个数字，那么目标数字一定在第(n+l-1)/l个数中
	target := start + (n+l-1)/l - 1
	// 最后转为在这个数字找到第x个数字的问题
	n -= (n - 1) / l * l
	x := target
	p := start
	for {
		n--
		if n == 0 {
			return x / p
		}

		x -= x / p * p
		p /= 10
	}
}
